package com.huangyi;
import java.util.*;

public class Main {
    public static void main(String[] args) {
        //数据流中的第 K 个大元素
        class KthLargest {
            private final PriorityQueue<Integer> pq; // 小根堆：堆顶是当前“前k大”中的最小者（即第k大）
            private final int k;

            public KthLargest(int k, int[] nums) {
                this.k = k;
                this.pq = new PriorityQueue<>(); // 默认小根堆
                for (int x : nums) {
                    pq.offer(x);
                    if (pq.size() > k) {
                        pq.poll(); // 只保留前k大
                    }
                }
            }

            public int add(int val) {
                pq.offer(val);
                if (pq.size() > k) {
                    pq.poll(); // 超出k就移除最小的，维持“前k大”
                }
                return pq.peek(); // 堆顶即第k大
            }
        }


        //前 K 个高频单词
        class Solution {
            public List<String> topKFrequent(String[] words, int k) {
                // 1) 统计词频
                Map<String, Integer> hash = new HashMap<>();
                for (String w : words) {
                    hash.put(w, hash.getOrDefault(w, 0) + 1);
                }

                // 2) 小根堆：更差的在堆顶
                PriorityQueue<Pair<String, Integer>> pq = new PriorityQueue<>(
                        (a, b) -> {
                            if (!a.getValue().equals(b.getValue())) {
                                return a.getValue() - b.getValue(); // 频率小的更差
                            }
                            return b.getKey().compareTo(a.getKey()); // 字典序大的更差
                        }
                );

                // 3) 遍历 map，维持堆大小 ≤ k
                for (Map.Entry<String, Integer> e : hash.entrySet()) {
                    pq.offer(new Pair<>(e.getKey(), e.getValue()));
                    if (pq.size() > k) {
                        pq.poll();
                    }
                }

                // 4) 出堆收集结果
                List<String> ans = new ArrayList<>();
                while (!pq.isEmpty()) {
                    ans.add(pq.poll().getKey());
                }

                // 5) 反转得到最终结果
                Collections.reverse(ans);
                return ans;
            }

            // 简单 Pair 实现（若无 javafx.util.Pair）
            static class Pair<K, V> {
                private final K key;
                private final V value;
                Pair(K k, V v) { this.key = k; this.value = v; }
                public K getKey() { return key; }
                public V getValue() { return value; }
            }
        }
    }
}